\chapter{Лекция 9. Нисходящий анализ}

\section{Введение}

Все что будет расмотрено в этой лекции будет относится именно к узкой области языков программирования. Вспомним
как мы убеждались, что произвольный КС-язык распознается НМА. Пусть у нас имеется грамматика

$$ G = \left(N,T,S,R\right) $$

НМА получался следующим образом

$$ A = \left(T, N \cup T, \lbrace q \rbrace, S, \delta \right) $$

где

$$ \delta \left(a, a\right) = \varepsilon $$
$$ \delta \left(\varepsilon, M\right) = \gamma, \text{ где } M \rightarrow \gamma \in R $$

цепочка допускается, если магазин опусташается (кстати, функция переходов выглядит так ущербно, так как нам
хватило всего одного состояния).

Такой автомат существенно недетерминирован и строит левый вывод. Кроме того, этот вывод будет нисходящим, т. е. он строит дерево вывода начиная с корня (стартового нетерминала). Такая конструкция вполне естественна, она сканирует
цепочку слева направо и постепенно из стратовго нетерминала расширяет дерево вывода вниз.

\section{Расшиенный магазинный автомат}

\begin{Def}
Расширенный магазинный автомат в отличие от НМА имеет функцию переходов следующего вида:

$ \delta' : Q \times X \cup \lbrace \varepsilon \rbrace \times \Gamma^{*} \rightarrow Q \times \Gamma^{*} $

обратите внимание, что эта функция зависит уже не только от верхнего магазинного символа, а цепочки на вершине
магазина. Кроме того, требуется, чтобы функция переходов $\delta'$ была конечной.

Кроме, того, очевидно, что расширенный автомат может не зависить от верхнего символа магазина и работать даже
с пустым магазином, а значит должен допускать цепочку по финальному состоянию.
\end{Def}

Покажем, что такой автомат ничего не добавляет к мощности языка. Построим НМА по такому расширенному автомату,
для правила функции $\delta'$ вида $q,x,\gamma \rightarrow q',\gamma'$, где $\gamma \not= \varepsilon$. Пусть
$\gamma = a_1 a_2 ... a_k$, тогда заведем набор правил функции $\delta$ следующего вида:

\[
	\begin{split}
		& q, x, a_1 \rightarrow q_1, \varepsilon \\
		& q_1, \varepsilon, a_2 \rightarrow q_2, \varepsilon \\
		& ... \\
		& q_k, \varepsilon, a_k \rightarrow q', \gamma'
	\end{split}
\]
таким образом мы промоделировали применение исходного правила расширенного автомата.

А правило вида $q, x, \varepsilon \rightarrow q', \gamma'$ заменяем на набор правил:

$$ q, x, a \rightarrow q', \gamma'a $$

где $a$ - все возможные символы, но при этом, чтобы предотвратить неприятность с пустым стеком, мы должны в самом начале положить на дно магазина некоторый специальный символ $Z$ и добавить правила следующего вида:

$$ q, x, Z \rightarrow q', \gamma'Z $$

Таким образом мы получили НМА по расширенному автомату, т. е. расширенный магазинный автомат не расширяет множества
допускаемых языков.

\section{Восходящий разбор}

Восходящий разбор собирает дерево вывода объединя уже распознаные узлы, т. е. находя в исходной цепочке правые 
части правил вывода и заменяя их на нетерминалы левой части.

Рассмотрим правый вывод цепочки $x + x * x$ в грамматике с правилами:

\[
	\begin{split}
		& S ::= S + T | T \\
		& T ::= T * F | F \\
		& F ::= (S) | x
	\end{split}
\]

\[
	\begin{split}
		& S \rightarrow S + T \rightarrow S + T * F \rightarrow S + T * x \\
		& \rightarrow S + F * x \rightarrow S + x * x \rightarrow T + x * x \\
		& \rightarrow F + x * x \rightarrow x + x * x
	\end{split}
\]

Теперь будем двигаться в обратном направлении, отыскивая правые части правил в цепочке и заменяя их, но
при этом допускаются только замены, переводящие правовыводимые цепочки опять в правовыводимые:

\[
	\begin{split}
		& x + x * x \rightarrow F + x * x \rightarrow T + x * x \rightarrow \\
		& S + x * x \rightarrow S + F * x \rightarrow S + T * x \rightarrow \\
		& S + T * F \rightarrow S + T \rightarrow S
	\end{split}
\]

т. е. в точности наш вывод в обратном порядке.

\begin{Def}
Пусть $S \Rightarrow^*_r \alpha \gamma \beta$ - правосторонний вывод, тогда $\alpha \gamma \beta$ сворачивается
к $\alpha A \beta$, если существует правило вывода $A \rightarrow \gamma$, такое преобразование называется сверткой по правилу $A \rightarrow \gamma$. Свертка нызывается правой, если цепочка $\alpha A \beta$ также 
правовыводима
\end{Def}

Вот такая последовательная правая свертка и дает нам разбор снизу вверх.

\section{Класс LL(k)}

Вернемся опять к выводу сверху вниз. Нам бы хотелось перейти от недетерминированного разбора с возвратами к
детерминированному. Пусть у нас для некоторого нетерминала $A$ есть несколько правил:

$$ A ::= \gamma_1 | \gamma_2 | ... | \gamma_k $$

если все цепочки $\gamma_i$ - начинаются с разного нетерминала, то очевидно, нет никакой определенности, LL(k)
обощает эту конструкцию.

\begin{Def}
Грамматика $G$ называется LL(k) грамматикой, если в процессе левого разбора строки, по заданному нетерминалу мы однозначно определяем используемое правило вывода посмотрев не более $k$ символов входной строки.
\end{Def}

Чтобы дать более формальное определение, потребуются некоторые дополнительные конструкции, но для начала
посмотрим детерминированный расширенный магазинный автомат для грамматики, зная, что она принадлежит классу
LL(k).

То, что грамматика принадлежит классу LL(k), то значит существует отображение

$$ N \times T^k \rightarrow (N \cup T)^* $$

имея такое отображение, мы запросто определеяем нужное правило вывода и то, что мы должны положить на вершину 
магазина, достаточно добавить выбор правила на основе такого отображения.

Наиболее употребительным является все-таки класс LL(1) с ним далее и будем работать.

\section{FIRST и FOLLOW}

\begin{Def}
$FIRST_k\left( \alpha \right) = \lbrace w \in T^* | \alpha \Rightarrow^* w v, |w| = k, v \in T^* \rbrace \cup \lbrace w \in T^* | \alpha \Rightarrow^* w, |w| < k \rbrace$
\end{Def}

Кстати, если все нетерминалы продуктивны (например, если из грамматики устранены все бесполезные символы), тогда
условие $v \in T^*$ не нужно, и построение множества $FIRST$ упрощается (по крайней меры мы приобретаем,
некоторый более разумный критерий остановки).

\begin{Def}
$FOLLOW_k\left(\alpha\right) = \lbrace w \in T* | S \Rightarrow^* u \alpha v, w \in FIRST_k(v) \rbrace$
\end{Def}

Имея эти два определения мы можем уже формально ввести класс LL(k) следующим образом:

\begin{Def}
Пусть $G$ - КС-грамматика, тогда $G \in LL(k)$ тогда и только тогда, когда для любых двух выводов:

$$ S \Rightarrow^*_l w A u \Rightarrow w \beta u \Rightarrow^*_l w x $$

и

$$ S \Rightarrow^*_l w A u \Rightarrow w \gamma u \Rightarrow^*_l w y $$

из того, что $FIRST_k(x) = FIRST_k(y)$ следует, что $\gamma = \beta$
\end{Def}

Можно сформулировать следующее утверждение:

$G \in LL(k)$ тогда и только тогда, когда для любой пары правил $A ::= \beta$ и $A ::= \gamma$ выполняется
условие $FIRST_k(\beta \alpha) \cap FIRST_k(\gamma \alpha) = \emptyset$ для любого $\alpha$, такого что $S \Rightarrow ^*_l w A \alpha$

Самый интересный (и один из самых простых) случаев - грамматика без $\varepsilon$-правил и $k = 1$, тогда
достаточно проверить, что $FIRST_1(\beta) \cap FIRST_1(\gamma) = \emptyset$

Если таки $\varepsilon$-правила таки присутствуют, тогда критерий преобразуется следующим образом:

$FIRST_1(\gamma FOLLOW_1(A)) \cap FIRST_1(\beta FOLLOW_1(A)) = \emptyset$

кажется, что для произвольного $k$ последние условие тоже верно, но увы, такой критерий для произвольного $k$
является достаточным, но не необходимым.

\section{Нисходящий разбор на практике}

На практике распространены ровно два способа: рекурсивный спуск и парсер/комбинатор. Вот их мы сейчас и рассмотрим.

\subsection{Рекурсивный спуск}

В общем случае данный метод производит анализ сверху вниз с возвратами, а главное его достоинство - естественность, анализатор фактически просто повторяет структуру грамматики. То есть каждому нетерминалу
грамматики сопоставлется некоторая процедура, которая пытается читать входной поток с заданной позиции, ссылаясь
на другие функции рекурсивно (или просто вызывая дургие функции для чтения входящих в правую часть правил 
нетерминалы).

Рассмотрим как пример следующую грамматику:

$$ S ::= () | (S) | SS $$

эта грамматика лево-рекурсивна, посему напрямую не разбирается в исходном виде рекурсивным спуском, преобразуем
ее к следующему виду:

$$ S ::= () | (S) | ()S | (S)S $$

кроме того, полезно заметить, что первые два правила и вторые два правила имеют одинаковый префикс, т. е.
можно записать эту же грамматику несколько короче, используя дополнительные операции (*, +):

$$ S ::= ()S? | (S)S? $$

или еще короче:

$$ S ::= \lbrace(S?)\rbrace+ $$
